W12. Graph Traversal

Author

Nikolai Kudasov

Published

April 7, 2026

1. Theory

1.1 Graphs as a Model

1.1.1 Why Graphs?

Most data structures studied previously — binary search trees, heaps, hash tables — are optimised for specific operations over general sets or ordered maps. Graphs take a different approach: instead of abstracting away structure, they model the inherent relationships in a problem directly. A graph makes the connections between objects first-class citizens of the data structure.

Graphs arise whenever a problem has a natural network interpretation: pages on the web link to one another, tasks depend on other tasks before they can start, routers forward packets to neighbouring routers, researchers co-author papers. Once a problem is cast as a graph, a large library of classical algorithms becomes available.

Typical graph problems include:

Shortest paths — finding the cheapest or fastest route between two points (navigation, network routing, planning).
Visiting all vertices — the Travelling Salesman Problem and its relaxations.
Minimum-cost connectivity — minimum spanning trees that connect all vertices with the least total edge cost.
Ordering under constraints — topological sort for scheduling tasks that have prerequisites.

1.1.2 Directed vs. Undirected Graphs

A graph consists of a finite set of vertices (also called nodes) and a set of edges, where each edge is a pair of vertices.

The nature of an edge depends on whether the relationship it represents is symmetric:

In an undirected graph, edges are unordered pairs . The relationship is symmetric: if is connected to , then is connected to . Examples: mutual friendship, co-authorship, bidirectional roads.
In a directed graph (or digraph), edges are ordered pairs and are drawn as arrows from to . The relationship is asymmetric: a flight from SFO to JFK does not imply a return flight. Examples: prerequisite constraints, one-way streets, social-media “follows”.

1.1.3 Adjacency, Paths, Cycles, and Weighted Graphs

Two vertices are adjacent if an edge connects them. In a directed graph, makes an out-neighbour of and an in-neighbour of .

A path from to is a sequence of vertices such that each consecutive pair is connected by an edge. A simple path visits no vertex more than once. A cycle is a path that starts and ends at the same vertex; a simple cycle visits no vertex more than once except the start/end.

A weighted graph assigns a numeric weight to every edge representing, for instance, a distance, cost, bandwidth, or latency. Shortest-path algorithms for weighted graphs generalise BFS and are covered later (e.g., Dijkstra’s algorithm).

1.2 Representing Graphs

1.2.1 Graph ADT

A dynamic graph structure must support both structural updates and queries. The core operations are:

insertVertex(v) — add a new isolated vertex.
insertEdge(u, v, w) — add edge between and (with optional weight ).
removeVertex(v) — delete and all incident edges.
removeEdge(e) — delete edge .
getEdge(u, v) — return the edge object between and , or NIL.
degree(v) — return the number of edges incident to .
iterateNeighbors(v) — iterate over all vertices adjacent to .

The right choice of representation depends on which operations dominate and on the graph density. A sparse graph has ; a dense graph has .

1.2.2 Edge-List Structure

The simplest representation maintains:

A vertex list — a doubly linked list of vertex objects; each object stores the vertex payload and a back-pointer into the list for removal.
An edge list — a doubly linked list of edge objects; each edge object stores references to its two endpoint vertices plus a back-pointer into the list.

Time complexities (with back-pointers):

Operation	Time
`insertVertex(v)`
`insertEdge(u, v, w)`
`removeEdge(e)`
`getEdge(u, v)`	— must scan the entire edge list
`degree(v)`	— must scan the entire edge list
`removeVertex(v)`	— must remove all incident edges

The edge-list structure is simple and mutation-friendly, but it is impractical for graphs that require frequent adjacency or degree queries.

1.2.3 Adjacency Lists

Each vertex stores an adjacency list: a list (or linked list) of edge objects incident to . With doubly linked adjacency lists and cross-pointers from each edge object back to its position in each endpoint’s list, removal becomes efficient.

Time complexities:

Operation	Time
`degree(v)`	— list length stored explicitly
`getEdge(u, v)`
`removeVertex(v)`	— remove from each neighbour’s list
`removeEdge(e)` where	without back-pointers; with

For an undirected graph: and . For a directed graph: . Adjacency lists are the standard choice for sparse graphs; the graph algorithms DFS, BFS, and topological sort all run in with this representation.

1.2.4 Adjacency Matrix

Store a matrix where holds the edge between vertex and vertex (or NIL / 0 if there is none, and the edge weight if the graph is weighted). A separate array of vertex objects maps labels to matrix indices and provides back-pointers.

	u	v	w	z
u	—	e	g	—
v	e	—	f	—
w	g	f	—	h
z	—	—	h	—

Time complexities:

Operation	Time
`insertEdge(u, v, w)`
`getEdge(u, v)`
`removeEdge(e)`
`degree(v)`	— or with explicit degree counters
`insertVertex(v)`	to resize the matrix; amortised with dynamic arrays
`removeVertex(v)`	with lazy deletion or row/column swap

The adjacency matrix shines when (dense graphs) and getEdge queries are frequent. It uses space, which is wasteful for sparse graphs.

1.2.5 Representation Comparison

Let and .

Operation	Edge list	Adjacency lists	Adjacency matrix
`getEdge(u,v)`
`degree(v)`		*	or *
`iterateNeighbors(v)`
`insertVertex`			/ amort.
`removeVertex`			/ amort.
`insertEdge`
`removeEdge`	**	**
Space

*With explicit degree counters. **Given a pointer to the edge object and doubly linked adjacency lists.

Rule of thumb: prefer adjacency lists for sparse graphs and algorithm correctness guarantees; prefer adjacency matrices when and you need edge existence queries.

1.3 Graph Traversals

1.3.1 Motivation for Traversal

A graph traversal visits every vertex reachable from a start vertex (or every vertex in the entire graph) in a systematic order. Traversals are fundamental subroutines used for:

Computing connected components in undirected graphs.
Checking reachability and finding paths.
Cycle detection — detecting back edges during DFS.
Discovering bridges and articulation points.
Building a graph lazily from implicit data (vertices and edges are discovered on the fly).

1.3.2 Connected Components

In an undirected graph, vertices and are connected if a path joins them. A connected component is a maximal subset such that every pair of vertices in is connected and no vertex outside has an edge into .

To find all connected components, run DFS (or BFS) starting from any unvisited vertex; every vertex reached belongs to the same component. Restart from the next unvisited vertex to find the next component. The total work is still .

1.4 Depth-First Search

1.4.1 DFS Algorithm

Depth-first search (DFS) explores as deep as possible before backtracking. The intuition: follow a path until you hit a dead end, then retrace your steps until you find an unexplored branch.

DFS can be implemented either recursively (the call stack plays the role of an explicit stack) or iteratively with an explicit stack:

DFS-EXPLICIT-STACK(G, start):
1  push start onto S
2  while S is not empty:
3      u = top of S
4      if u is unvisited:
5          mark u as visited
6          push an unvisited neighbour of u (if any)
7      else if u has no unvisited neighbours:
8          pop u from S
9      else:
10         push an unvisited neighbour of u

The formal CLRS pseudocode uses the recursive form with discovery and finish timestamps:

DFS(G):
1  for each vertex u in G.V:
2      u.color = WHITE;  u.π = NIL
3  time = 0
4  for each vertex u in G.V:
5      if u.color == WHITE:
6          DFS-VISIT(G, u)

DFS-VISIT(G, u):
1  time = time + 1;  u.d = time;  u.color = GRAY
2  for each v in G.Adj[u]:
3      if v.color == WHITE:
4          v.π = u
5          DFS-VISIT(G, v)
6  time = time + 1;  u.f = time;  u.color = BLACK

Each vertex cycles through three colours: WHITE (undiscovered), GRAY (discovered, still being processed), BLACK (fully finished). The timestamp records when was first discovered; records when ’s subtree was fully explored. For any edge in the DFS forest, the interval properly contains .

Visited representation. To check whether a vertex is visited, use a boolean array indexed by vertex number, or store a colour field directly in the vertex object.

1.4.2 DFS Example

Consider the following undirected graph with vertices –. Edges: , , , , , , , , .

Starting DFS at (with the convention of exploring neighbours in alphabetical order):

Step	Event	Stack (top → bottom)
1	visit
2	visit
3	visit
4	backtrack
5	visit
6	backtrack twice
7	visit
8	visit
9	visit
10	visit
11	backtrack twice
12	visit
13	unwind

DFS visit order: .

1.4.3 DFS Analysis

With adjacency lists: initialising colours takes . Each DFS-VISIT call processes edges. Since each edge is examined at most twice (once per endpoint for undirected graphs):

With an adjacency matrix: each call to DFS-VISIT(G, u) scans all potential neighbours regardless of actual degree:

1.4.4 DFS Timestamps and Edge Types

The discovery/finish timestamps and enable classification of every edge in a directed graph:

Tree edge — is discovered via ; was WHITE.
Back edge — is an ancestor of in the DFS tree; is GRAY when is explored. Back edges indicate directed cycles.
Forward edge — is a descendant of already finished; is BLACK with .
Cross edge — is neither ancestor nor descendant; BLACK with .

The parenthesis theorem states: for two vertices and , exactly one of three cases holds — and are disjoint (neither is an ancestor of the other), or one interval properly contains the other (one is an ancestor).

1.5 Breadth-First Search

1.5.1 BFS Algorithm

Breadth-first search (BFS) expands level by level outward from the source vertex. Instead of going deep, it processes all neighbours before moving further away. BFS uses a queue (FIFO) to maintain the frontier.

BFS(G, s):
1  for each vertex u in G.V - {s}:
2      u.color = WHITE;  u.d = ∞;  u.π = NIL
3  s.color = GRAY;  s.d = 0;  s.π = NIL
4  Q = ∅;  ENQUEUE(Q, s)
5  while Q ≠ ∅:
6      u = DEQUEUE(Q)
7      for each v in G.Adj[u]:
8          if v.color == WHITE:
9              v.color = GRAY;  v.d = u.d + 1;  v.π = u
10             ENQUEUE(Q, v)
11     u.color = BLACK

Line 7 processes all neighbours of each dequeued vertex exactly once. The queue ensures vertices at distance are all processed before any vertex at distance .

1.5.2 BFS Example

Using the same graph from the DFS example, starting BFS at :

Step	Event	Queue (front → back)
0	init
1	visit
2	visit
3	visit
4	visit
5	visit
6	visit
7	visit
8	visit
9	visit

BFS visit order: .

The BFS naturally partitions vertices into distance layers :

Yellow: ; light blue: ; light grey-blue: ; green: .

1.5.3 BFS Analysis

The initialisation loop at lines 1–4 takes . Each vertex is enqueued and dequeued at most once. The inner loop at line 7 iterates over all edges incident to ; summing over all dequeued vertices visits each edge at most twice (undirected) or once (directed). Thus:

With an adjacency matrix, scanning each row takes per vertex, giving overall.

1.5.4 Shortest Paths in Unweighted Graphs

BFS computes the shortest-path distance — the minimum number of edges on any path from to — for all vertices . The field stores this value after BFS completes; the field stores the predecessor on the shortest path, enabling path reconstruction.

Why BFS gives shortest paths. BFS processes vertices in non-decreasing order of their distance from . When vertex is first discovered (coloured GRAY), it is reached via a path of exactly edges, which is optimal because any shorter path would have discovered earlier.

Why BFS fails for weighted shortest paths. BFS counts hops, not weights. Consider three vertices , , with edges (weight 1), (weight 1), and (weight 100). BFS reports (one hop), but the true minimum-weight path has total weight 2. For weighted graphs, use Dijkstra’s algorithm instead.

1.6 DFS vs. BFS

Property	DFS	BFS
Data structure	Stack (explicit or call stack)	Queue
Exploration style	Deepest-first, then backtrack	Layer by layer from source
Asymptotic time	adj. lists	adj. lists
Asymptotic time	adj. matrix	adj. matrix
Shortest paths	No (in general)	Yes (unweighted only)
Cycle detection	Yes (back edges)	Less direct
Topological sort	Yes (via finish times)	No
Memory usage	stack depth	queue size
Extra info	Discovery/finish times, edge types	Distance labels, BFS tree

Both algorithms are complete on finite graphs when every vertex is visited: running DFS or BFS from each unvisited vertex ensures all connected components are processed. DFS’s recursive nature makes it natural for problems that exploit the parenthesis structure of finish times (cycle detection, topological sort, SCCs). BFS is the canonical choice whenever layer-by-layer expansion or minimum hop counts are needed.

1.7 Topological Sorting

1.7.1 Directed Acyclic Graphs

A directed acyclic graph (DAG) is a directed graph with no directed cycles. DAGs arise naturally whenever a problem has precedence constraints: course prerequisites, build-system dependencies, spreadsheet recalculation order, or instruction scheduling in compilers. If the constraint graph contained a cycle, the constraints would be mutually contradictory (task must finish before , and before — impossible).

1.7.2 Topological Order

A topological sort of a DAG is a linear ordering of all vertices such that for every directed edge , vertex appears before in the ordering. Equivalently: arrange all vertices on a line so that every edge points left-to-right.

A topological order exists if and only if the graph is a DAG. Topological orders are generally not unique — any order that respects all edge constraints is valid. The number of valid orders ranges from 1 (a single directed chain) to (no edges at all).

1.7.3 DFS-Based Topological Sort

Algorithm (Cormen et al. 2022, §20.4):

TOPOLOGICAL-SORT(G):
1  run DFS(G) to compute finish times v.f for all v
2  as each vertex is finished, prepend it to a linked list
3  return the linked list

Why it works. In a DAG, DFS produces no back edges (a back edge would imply a cycle). For every directed edge explored during DFS: if was WHITE when is first encountered, finishes before , so ; if was already BLACK (a cross or forward edge), likewise. In both cases , so appears earlier in the sorted list (which is ordered by decreasing finish time). Thus every edge points from a vertex with larger finish time to one with smaller finish time — exactly the required direction.

Running time: — just the cost of DFS.

The dressing-order DAG illustrates a canonical example:

Numbers in parentheses are DFS discovery/finish timestamps from one execution. Sorted by decreasing finish time: socks (14) → pants (12) → shoes (11) → shirt (8) → tie (7) → belt (4) → jacket (3).

1.7.4 When Topological Sort Fails

If has a directed cycle, no linear ordering can satisfy all edge constraints — there will always be at least one edge pointing “backward” in any arrangement. DFS detects this automatically: a back edge (reaching a GRAY vertex) is found if and only if the graph has a directed cycle. The algorithm can be augmented to output the cycle as a witness.

2. Definitions

Graph : a finite set of vertices and a set of edges (unordered or ordered pairs of vertices).
Undirected graph: a graph in which edges are unordered pairs , representing symmetric relationships.
Directed graph (digraph): a graph in which edges are ordered pairs , representing asymmetric relationships.
Weighted graph: a graph in which each edge carries a numeric weight (distance, cost, etc.).
Adjacent: two vertices are adjacent if an edge connects them directly.
Path: a sequence of vertices where consecutive pairs share an edge.
Simple path: a path that visits no vertex more than once.
Cycle: a path that starts and ends at the same vertex.
Connected component (undirected): a maximal subset of vertices in which every pair is connected by a path.
Sparse graph: a graph with .
Dense graph: a graph with .
Edge-list structure: graph representation maintaining a list of vertex objects and a list of edge objects with back-pointers.
Adjacency list: graph representation where each vertex stores a list of its incident edges or neighbouring vertices.
Adjacency matrix: graph representation using a matrix where encodes the edge between vertices and .
DFS (depth-first search): a graph traversal that explores as deep as possible before backtracking, using a stack or recursion.
BFS (breadth-first search): a graph traversal that expands level by level from a source using a queue; computes shortest hop distances in unweighted graphs.
Discovery time : the DFS timestamp when vertex is first reached (coloured GRAY).
Finish time : the DFS timestamp when all of ’s descendants are fully explored (coloured BLACK).
Tree edge: an edge used by DFS to discover for the first time.
Back edge: an edge to an ancestor of in the DFS tree; indicates a directed cycle.
Forward edge: an edge to a non-tree descendant already finished (directed graphs only).
Cross edge: an edge between vertices in different DFS subtrees (directed graphs only).
BFS tree: the spanning tree formed by the tree edges of a BFS traversal; each tree edge represents the shortest path from the source.
DAG (directed acyclic graph): a directed graph containing no directed cycles; used to model precedence constraints.
Topological sort: a linear ordering of the vertices of a DAG such that every directed edge has before in the ordering.

3. Formulas

DFS/BFS time complexity (adjacency lists):
DFS/BFS time complexity (adjacency matrix):
Handshaking lemma (undirected):
Maximum edges (undirected):
Maximum edges (directed):
Parenthesis theorem: for every pair , exactly one holds: and are disjoint, or one properly contains the other.
Topological sort rule: output vertices in decreasing order of DFS finish time .
Shortest path via BFS: after BFS(G, s) (unweighted graph only).
Expected degree (Erdős–Rényi): if each edge exists independently with probability , then .
Expected number of edges (Erdős–Rényi): .

4. Practice

4.1. Enumerate Topological Orderings and Removable Edges (Problem Set 10, Task 1)

Consider the following directed acyclic graph :

(a) Write down all valid topological orderings of .

(b) List all edges that can be deleted from without changing the set of valid topological orderings.

(c) What is the maximum possible number of distinct topological orderings for a DAG with 9 vertices? Briefly justify.

(d) What is the maximum possible number of distinct topological orderings for a DAG with 7 vertices and exactly 10 edges? Briefly justify.

Click to see the solution

(a) All topological orderings.

First, identify structural constraints from the edges:

has no incoming edges → must come first.
and both require only → either can come second.
requires both and → comes after both.
requires → comes after .
requires and (through B→F and E→F); requires and (through C→G and E→G) → and may appear in either order after .
requires both and → must come last.

The only freedom is: (i) the relative order of and , and (ii) the relative order of and after . This gives valid orderings:

Answer: exactly 4 valid topological orderings.

(b) Removable edges.

An edge can be removed without affecting the set of topological orderings if and only if the constraint “ before ” is already implied by some other directed path from to (i.e., the edge is transitive). Such edges are:

: already forced by and .
: already forced by .
: already forced by .

Removing any of these three edges leaves the ordering set unchanged. Every other edge provides a constraint not reachable via another path and cannot be removed.

Answer: , , .

(c) Maximum orderings for 9 vertices.

The maximum is . This is achieved by the DAG with no edges: with zero constraints, every permutation of the 9 vertices is a valid topological ordering. Adding any edge eliminates at least one permutation (any ordering where precedes ), so the edgeless graph maximises the count.

(d) Maximum orderings for 7 vertices and exactly 10 edges.

The maximum is . The optimal structure is a complete bipartite DAG: let (2 sources) and (5 sinks), with all edges directed from to .

The only constraint is that both and must appear before all five . There are ways to order the sources and ways to order the sinks, giving valid orderings. Any other 10-edge DAG on 7 vertices would impose at least one additional constraint within a group, reducing the count below 240.

4.2. Probabilistic Analysis of BST-Based Adjacency Structure (Problem Set 10, Task 2)

Consider a large undirected graph whose vertex labels are integers. The graph is stored using an adjacency-list variant: for each vertex , its set of neighbours is kept in a binary search tree (BST) keyed by neighbour references. Vertex arguments are references to vertex objects. Assume every unordered pair of distinct vertices exists as an edge independently with probability , and assume worst-case time for all BST operations.

(a) Compute .

(b) Compute for a randomly chosen vertex .

(c) Compute .

(d) Compute .

(e) Compute .

(f) Compute .

Click to see the solution

(a) Expected number of edges.

There are possible unordered pairs. Each exists independently with probability . By linearity of expectation:

(b) Expected degree.

Vertex may be connected to each of the other vertices independently with probability . Each indicator variable equals 1 if edge exists, 0 otherwise. By linearity of expectation:

(c) Expected time of areAdjacent(v, u).

This operation searches for in ’s BST. Under worst-case BST behaviour (the BST may be a sorted chain of all neighbours), the search takes . Taking expectations:

(d) Expected time of removeEdge(from, to).

Since the graph is undirected, removeEdge must delete to from from’s BST and delete from from to’s BST. Each deletion costs in the worst case. Both endpoints have the same expected degree:

(e) Expected time of removeVertex(v).

removeVertex(v) must (i) remove from each neighbour ’s BST (costing per neighbour) and (ii) delete ’s own BST. There are neighbours. Given that is a neighbour of , vertex has one guaranteed edge to plus each of the remaining vertices independently with probability :

The total expected work over all neighbours plus the deletion of ’s BST is:

(f) Expected time of iterateNeighbors(v).

Iterating over all neighbours requires visiting every node of ’s BST exactly once (e.g., via an in-order traversal), costing :

4.3. Construct a Tree Not Achievable by BFS or DFS (Problem Set 10, Task 3)

Exhibit a directed graph , a root , and a spanning tree with root such that all of the following hold:

is weakly connected (the underlying undirected graph is connected).
is weakly connected.
.
cannot be the BFS spanning tree from under any ordering of adjacency lists.
cannot be the DFS spanning tree from under any ordering of adjacency lists.
Extra credit: for every fixed adjacency ordering, the BFS and DFS spanning trees are different from each other.

Click to see the solution

Construction. Let with as root, and

Bold purple: tree edges of . Dashed gray: remaining edges of .

Checking the constraints.

Weak connectivity. The underlying undirected graph connects all five vertices: reaches directly; and are connected bidirectionally; reaches . is a spanning tree so it is also weakly connected.
is not a BFS tree. BFS from discovers at distance 1 via the direct edge . But in , vertex is a child of (distance 2 from ). Since BFS always assigns each vertex its true shortest-path distance, can never appear at distance 2 in any BFS tree — so is not achievable by BFS for any adjacency ordering.
is not a DFS tree. In , both and are direct children of . However, contains the edges and . In any DFS from , whichever of or is visited first (say ) will reach the other ( via ) before DFS returns to , making a descendant of , not a sibling. Therefore the edge can never be a tree edge for any adjacency ordering — so is not achievable by DFS.
Extra credit: BFS DFS for every adjacency ordering. The unique BFS tree from is (all four out-neighbours discovered at depth 1). Every DFS tree must use either or as a tree edge (because of the mutual edges between and ). Therefore no DFS tree can coincide with the BFS tree (which has only edges out of ). This holds for all adjacency orderings.

4.4. Choose a Graph Representation (Lecture 10, Task 1)

For each scenario, choose among edge list, adjacency lists, and adjacency matrix, and justify in one sentence:

A very dense graph with frequent “is an edge?” queries and rare structural changes.
A sparse social graph with frequent neighbour iteration.
A dynamic graph with frequent edge insert/delete, given pointers to edge objects.

Click to see the solution

Adjacency matrix. For dense graphs () the space cost is acceptable, and getEdge(u,v) runs in — exactly what is needed when edge-existence queries dominate.
Adjacency lists. A sparse social graph has , so an adjacency matrix would waste space. Iterating over the neighbours of vertex takes with adjacency lists versus with an adjacency matrix.
Edge list with back-pointers. With a pointer to the edge object, removeEdge runs in (splice out from the doubly linked edge list) and insertEdge is also . Adjacency lists would require to find and remove the cross-references; adjacency matrices support removal only if you forego the edge-object abstraction.

4.5. Alternative BFS Order and Layer Sets (Lecture 10, Task 2)

On the example graph (vertices –, start at ), give a BFS visit order that differs from the table in the lecture while still being valid under the “enqueue all undiscovered neighbours” rule. Then state the layer sets .

Click to see the solution

The layer sets are uniquely determined by shortest-path distances and do not depend on tie-breaking:

Within each layer the order of processing depends on the order in which neighbours are enqueued. One alternative valid BFS order (enqueue ’s neighbours in the order instead of ):

Verification: is dequeued first at layer 1 (’s neighbour), then , then ; from we enqueue (since is not yet visited at this point from , but is adjacent to as well — exact order depends on edge ordering), etc. Any order that processes all vertices before any vertex is valid; the layer partition is fixed.

4.6. Topological Sort on a Small DAG (Lecture 10, Task 4)

Perform topological sort on the DAG with vertices and edges by running DFS and listing vertices by decreasing finish time. Is the answer unique?

Click to see the solution

Step 1 — draw the DAG:

Vertex 1 is the unique source (no incoming edges); vertex 4 is the unique sink (no outgoing edges).

Step 2 — run DFS (starting at 1, then 2 before 3 in the adjacency list order):

Event	Timestamps
Discover 1
Discover 2 (from 1)
Discover 4 (from 2)
Finish 4
Finish 2
Discover 3 (from 1)
4 is already BLACK	—
Finish 3
Finish 1

Step 3 — sort by decreasing finish time:

Is the answer unique? No. Vertices 2 and 3 are independent (neither depends on the other). If DFS had visited 3 before 2, it would produce the equally valid order . Both orderings satisfy all edge constraints: before and , and and both before .

4.7. DFS Timestamps: Counterexample to a False Implication (Lecture 10, Task 5)

Give a counterexample to: If a directed graph contains a path from to , and a DFS yields , then is a descendant of in the DFS forest.

Click to see the solution

Key idea. A counterexample requires a directed path from to that passes through a GRAY (ancestor) vertex — a back edge from to an ancestor of , followed by a tree edge from to . When DFS-VISIT() encounters the back edge , vertex is GRAY and is skipped; remains undiscovered until DFS backtracks to and processes after has already finished. This gives (premise holds) while ends up as a sibling of , not a descendant.

Counterexample. Let , .

Run DFS starting at , with ’s adjacency list in order :

Event	Time
Discover
Discover (via )
Explore : is GRAY — back edge, skip	—
Finish
Discover (via )
Finish
Finish

Verification. The directed path exists in . We have — the premise holds. Yet is discovered from (not from ), so is a child of and a sibling of in the DFS tree. Thus is not a descendant of , falsifying the conjecture.

4.8. DFS Finish Times: Another False Implication (Lecture 10, Task 6)

Give a counterexample to: If contains a directed path from to , then every DFS of satisfies .

Click to see the solution

Key idea. The same construction from Task 5 serves here. When the path from to goes through a GRAY ancestor and that ancestor’s edge to is explored after finishes, we get — directly falsifying the claim.

Counterexample. Same graph: , . Same DFS run (adjacency order at ):

The directed path exists. Checking the claim: , so is false.

Why this works. The edge is a back edge (to the GRAY ancestor ); DFS skips it and finishes at time 3. Only then does DFS-VISIT() resume and discover at time 4. The path from to crosses outside ’s DFS subtree via this back edge, allowing to be discovered entirely after finishes.

4.9. Implement Iterative DFS (Lecture 10, Task 7)

Rewrite DFS/DFS-VISIT replacing recursion with an explicit stack. The iterative version must replicate the discovery/finish timestamps of the recursive version exactly.

Click to see the solution

The key challenge is replicating the recursive call-return mechanism: when DFS-VISIT returns from a recursive call on child , execution continues scanning ’s adjacency list from the next neighbour after . The standard technique pushes a resume state — vertex and the index of the next neighbour to examine — instead of pushing a bare vertex.

DFS-ITERATIVE(G):
1  for each u in G.V:
2      u.color = WHITE;  u.π = NIL
3  time = 0
4  for each u in G.V:
5      if u.color == WHITE:
6          S = empty stack
7          push (u, 0) onto S            // (vertex, next-neighbour index)
8          time = time + 1
9          u.d = time;  u.color = GRAY
10         while S not empty:
11             (v, i) = top of S
12             if i < |G.Adj[v]|:
13                 w = G.Adj[v][i]
14                 S.top = (v, i + 1)    // advance the resume index
15                 if w.color == WHITE:
16                     w.π = v;  w.color = GRAY
17                     time = time + 1;  w.d = time
18                     push (w, 0) onto S
19             else:
20                 pop S                  // v is finished
21                 time = time + 1;  v.f = time;  v.color = BLACK

How it works. The stack frame represents: “we are in the middle of DFS-VISIT for , and the next unexamined neighbour is .” When a WHITE neighbour is found, we push (start examining ’s adjacency list from the beginning) before incrementing in ’s frame. When all neighbours of are exhausted (), is finished and popped.

Maximum stack depth. On a graph consisting of a single directed chain , the stack grows to depth (one frame per vertex along the chain). So the worst-case stack depth is , matching the maximum recursion depth of the recursive version.